In this paper we perform an extensive theoretical and experimental study on common synopsis construction algorithms, with emphasis on wavelet based techniques, that take under consideration query workload statistics. Our goal is to compare, ""expensive"" quadratic time algorithms with ""cheap"" near-linear time algorithms, particularly when the latter are not optimal and/or not workload-aware for the problem at hand. Further, we present the first known algorithm for constructing wavelet synopses for a special class of range-sum query workloads. Our experimental results, clearly justify the necessity for designing workload-aware algorithms, especially in the case of range-sum queries. Copyright 2006 ACM.
展开▼
